package com.clstu.leetcode;

import java.util.HashMap;
import java.util.List;
import java.util.Stack;

/**
 * 研究并查集结构,手写一个并查集结构的例子
 */
public class UnionFind {

    public static void main(String[] args) {
        System.out.println("djfs;lf0");
    }

    //将每一个元素包装一个圈,叫做元素,方便并查集统一使用
    public static class Element<V>{
        public V value;

        //构造器
        public Element(V value){
            this.value = value;
        }
    }


    //并查集结构(事先就要将全部的元素加进来,后面不允许查没有的元素!!!!!!!)
    public static class UnionFindSet<V>{

        //维护三个map
        //检查元素是否存在,初始化时需要提供所有的元素
        public HashMap<V,Element<V>> elementMap;
        //核心结构,靠这个判断是否时同一个最高层来判断是否时同一集合
        public HashMap<Element<V>,Element<V>> fatherMap;
        //一个最高层所管理的元素个数,即一个集合的元素个数
        public HashMap<Element<V> ,Integer> sizeMap;

        public UnionFindSet(List<V> list){
            elementMap = new HashMap<>();
            fatherMap = new HashMap<>();
            sizeMap = new HashMap<>();
            //初始化
            for (V v : list) {
                //给每个元素都包上一层圈(Element<V>d的圈)
                Element<V> element = new Element<>(v);
                elementMap.put(v,element);
                fatherMap.put(element,element);
                sizeMap.put(element,1);
            }
        }

        //编写方法,得到代表元素(最顶元素)
        public Element<V> getHead(V value){
            Stack<Element<V>> stack = new Stack<>();
            //找到最顶元素
            Element<V> element = elementMap.get(value);
            while (element!=fatherMap.get(element)){
                stack.push(element);
                element = fatherMap.get(element);
            }
            //扁平化,加速下一次查找head
            while (!stack.isEmpty()){
                fatherMap.put(stack.pop(),element);
            }
            return element;
        }

        //编写方法,合并两个元素到一个集合
        public void union(V value1,V value2){
            //先判断是否存在这个并查集里面
            if(elementMap.containsKey(value1) && elementMap.containsKey(value2)){
                //得到头节点
                Element<V> head1 = getHead(value1);
                Element<V> head2 = getHead(value2);
                //比较谁的size大
                Integer size1 = sizeMap.get(head1);
                Integer size2 = sizeMap.get(head2);
                //得到大的
                Element<V> bigger = size1>size2 ? head1:head2;
                Element<V> smaller = bigger == head1? head2:head1;
                //小的挂到大的下面
                fatherMap.put(smaller,bigger);
                sizeMap.put(bigger,size1+size2);
                sizeMap.remove(smaller);
            }
        }

        //编写方法,判断两个元素是否在同一个集合
        public boolean isSameSet(V value1,V value2){
            //如果时同一个最顶元素,则两个元素一定在同一个集合
            //需要先判断传入的元素在不在整个并查集里面
            if(elementMap.containsKey(value1) && elementMap.containsKey(value2)) {
                return getHead(value1) == getHead(value2);
            }
            //如果在集合里直接返回false
            return false;
        }
    }

}



class Solutionxxx {

    private int rows;
    private int cols;

    public int numIslands(char[][] grid) {
        rows = grid.length;
        if (rows == 0) {
            return 0;
        }
        cols = grid[0].length;

        // 空地的数量
        int spaces = 0;
        UnionFind unionFind = new UnionFind(rows * cols);
        int[][] directions = {{1, 0}, {0, 1}};
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '0') {
                    spaces++;
                } else {
                    // 此时 grid[i][j] == '1'
                    for (int[] direction : directions) {
                        int newX = i + direction[0];
                        int newY = j + direction[1];
                        // 先判断坐标合法，再检查右边一格和下边一格是否是陆地
                        if (newX < rows && newY < cols && grid[newX][newY] == '1') {
                            unionFind.union(getIndex(i, j), getIndex(newX, newY));
                        }
                    }
                }
            }
        }
        return unionFind.getCount() - spaces;
    }

    private int getIndex(int i, int j) {
        return i * cols + j;
    }

    private class UnionFind {
        /**
         * 连通分量的个数
         */

        //岛屿数量
        private int count;
        private int[] parent;

        public int getCount() {
            return count;
        }

        public UnionFind(int n) {
            this.count = n;
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        //找到头节点
        private int find(int x) {
            while (x != parent[x]) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }

        public void union(int x, int y) {
            int xRoot = find(x);
            int yRoot = find(y);
            if (xRoot == yRoot) {
                return;
            }
            parent[xRoot] = yRoot;
            count--;
        }
    }
}